#include"cds_rbtree.h"
#include<stdlib.h>
#include<stdio.h>
#include<time.h>

//去掉终端行模式,关回显
#define char_input() do{\
    system("stty raw");\
    system("stty -echo");\
}while(0)

//恢复终端行模式,开回显
#define line_input() do{\
    system("stty cooked");\
    system("stty echo");\
}while(0)

#define NR 1000000
int len;
unsigned long keys[NR];

//用户数据结构
typedef struct data{
    rbnode_t entry; //rbtree树节点
    unsigned long data;//数据域
} data_t;

//用户定义的生成key的函数,要使用红黑树，用户必须为每种数据类型定义一个这样的函数传入树结构
unsigned long create_key(rbnode_t * node ){
    return rbtree_entry(node,data_t, entry)->data;
}

void destroy(rbnode_t * node ){
    
    data_t * data = rbtree_entry(node,data_t,entry);
    printf("free the %lu address: %p\n",data->data, data);
    free(data);
}

void travel(rbnode_t * node ){
    data_t * data = rbtree_entry(node,data_t,entry);
    printf("%lu",data->data); 
}

void insert_random_datas(rbtree_t * tree, unsigned long n){
    time_t t;
    time(&t);
    srand(t);
    len=0;
    for(int i=0;i<n;i++){
        unsigned long value = rand()%1000000;
        data_t * data = malloc(sizeof(data_t));
        data->data = 100+value;
        rbnode_t * ret = rbtree_insert(tree, &data->entry);
        if(ret){
            i--;
        }else{
            keys[len++] = data->data;
        }
    }
}

int main(void){
    
    rbtree_t *tree = malloc(sizeof(rbtree_t));
    //初始化红黑树
    RBTREE_INIT(tree,create_key); 
    /*
     *  红黑树示例:
     *
     *      插入顺序: 73,89,26,86,41,88,90,91,99,38,87,77,66,55
     *      最终的树形态如下图:
     *                               30(b)
     *                              /      \
     *                             /         \
     *                            /            \
     *                           /               \
     *                          15(b)             70(b)
     *                         / \                /    \
     *                        /   \              /       \
     *                       /     \            /          \
     *                      10(b)  20(b)       60(r)        85(b) 
     *                     /                  /   \         /   \
     *                    /                  /     \       /     \
     *                   5(r)               50(b)  65(b) 80(r)    90(r)
     *                                     /   \
     *                                    /     \
     *                                  41(r)   55(r) 
     */
    unsigned long arr[] = {10,85,15,70,20,60,30,50,65,80,90,40,5,55};
    
    printf("数组长度:%d\n",sizeof(arr)/sizeof(unsigned long)); 
    //依次插入数组中的数到红黑树中
    for(int i=0;i<sizeof(arr)/sizeof(unsigned long); i++){
        data_t * dptr = malloc(sizeof(data_t));
        dptr->data = arr[i];
        rbtree_insert(tree,&dptr->entry); 
    }
    
    //顺序遍历红黑树:
    rbnode_t * pos;
    rbtree_for_each(pos, tree){
        data_t * pdtr = rbtree_entry(pos,data_t, entry);
        printf("pdtr->data=%lu\n",pdtr->data);
    }
    printf("一共有%d个元素\n",tree->size);
   
    int loop = 1;
    while(loop){
        unsigned long key;
        printf("[t]: level travel; [r]: insert more random datas; [s]: search; \n[i]: insert; [d]: delete; [c]: clear; [q]: quit; [m]: middle order travel; \n[b]: check the red-black tree balance; [D]:delete the last time insert datas by selecting 'r'\n请输入:\n");
        char_input();
         
        char ch;
        do{
            ch = getchar();
        }while(ch==13 || ch==10);
     
        line_input();
        switch( ch ){
            
            case 's': //搜索
                printf("输入key:\n");
                scanf("%lu",&key);
                rbnode_t * n1 = rbtree_search(tree, key);

                break;
            case 'i': //插入
                printf("输入要插入到数:\n");
                scanf("%lu",&key);
                data_t * pd = malloc(sizeof(data_t));
                pd->data = key;
                rbtree_insert(tree,&pd->entry); 
                break;
            case 'm': // middle order travel
                rbtree_travel_middle(tree,travel); 
                printf("一共有%d个数\n",tree->size);
                break;
            case 'r': //插入多个随机数
                printf("请输入要插入的数量:\n");
                scanf("%lu",&key);
                insert_random_datas(tree, key);                 
                rbtree_check_balance(tree);
                break;
                /*
            case 'e':
                {
                    unsigned long k1;
                    unsigned long k2;
                    printf("输入两个节点的key:\n");
                    scanf("%lu%lu",&k1,&k2);
                    rbnode_t * n1 = rbtree_search(tree, k1);
                    rbnode_t * n2 = rbtree_search(tree, k2);
                    rbtree_exchange_two_nodes(tree, n1, n2 );
                }
                break;
                */
            case 'd': //删除
                {
                    printf("请输入要删除的key:\n");
                    scanf("%lu",&key);
                    rbnode_t * dnode = rbtree_search(tree,key);
                    if(!dnode){
                        printf("您要删除的key:[%lu]不存在\n",key);
                        break;
                    }
                    rbtree_del(tree, dnode);
                    free(rbtree_entry(dnode,data_t,entry));
                }
                break;
            case 'D': //删除多个数
                {
                    int i=0;
                    for(;i<len;i++){
                        //printf("将要删除%lu\n",keys[i]);
                        rbnode_t * dnode = rbtree_search(tree,keys[i]);

                        if(!dnode){
                            printf("您要删除的key:[%lu]不存在\n",keys[i]);
                            continue;
                        }
                        rbtree_del(tree, dnode);
                        free(rbtree_entry(dnode,data_t,entry));
                    }
                    printf("一共删除了%d个数据\n",i);
                }
                break;
            case 'c': //清空红黑树
                rbtree_clear(tree, destroy);
                break;
            case 'b': //检测红黑树是否平衡
                rbtree_check_balance(tree);
                printf("the red-black tree is balance now!\n");
                break;
            case 't': //层次遍历红黑树
                rbtree_travel_level(tree, travel);
                putchar('\n');
                printf("一共有%d个数\n",tree->size);
                break;
            case 'q': //退出程序
                loop = 0;
                break;
        }
    }

    return 0;
}
